package algorithm.dp;

import java.util.ArrayList;
import java.util.List;

public class test {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    class Solution {
        public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
            find(root, target, K);
            return res;
        }

        public int find(TreeNode node, TreeNode target, int k) {
            if (node == null) {
                return k;
            }
            if (node.val == target.val) {
                find(node, 0, k);
                return k - 1;
            }
            int targetK = find(node.left, target, k);
            if (targetK >= 0 && targetK < k) {
                find(node.right, target, targetK);
            }
            targetK = find(node.right, target, k);
            if (targetK >= 0 && targetK < k) {
                find(node.left, target, targetK);
            }
            return targetK;
        }

        List<Integer> res = new ArrayList<>();

        public void find(TreeNode node, int level, int k) {
            if (node == null) {
                return;
            }
            if (level == k) {
                res.add(node.val);
            }
            if (level < k) {
                find(node.left, level + 1, k);
                find(node.right, level + 1, k);
            }
            if (level > k) {
                return;
            }
        }
    }
}
